//permutation of string

#include <string>
#include <iostream>
using namespace std;


//recursive 
int permutation(string s, const string cs, bool used[])
{
  static int c = 0;//count of recursive call
  c++;
  static int count = 0;
  if (s.length() == cs.length()) { //base case
    count++;
    cout<<count<<"\t"<<s<<endl;
    return c;
  }
  else {//recursive case
    for(int i = 0;i<(int)cs.length();i++) {
      if(used[i] == false){ //find the first unused char
// 	s+=cs[i]; //completely wrong, don't change s

	used[i] = true;
	permutation(s+cs[i],cs,used);
	used[i] = false;
      }
      else {
	continue;
      }
    }
    return c;
  }
}

int permutation2(string s, const string cs, bool used[]) //better
{
  static int c = 0;//count of recursive call
  c++;
  static int count = 0;
 
//recursive case
  for(int i = 0;i<(int)cs.length();i++) {
    if(used[i] == false){ //find the first unused char
      if (s.length() == cs.length() - 1) { //base case
	count++;
	cout<<count<<"\t"<<s + cs[i]<<endl;
	return c;
      }
      else { //recursive case
	used[i] = true;
	permutation2(s+cs[i],cs,used);
	used[i] = false;
      }
    
    }
  }//for
  return c;
}

int main(int argc, char *argv[])
{
  string cs;
  if(argc == 2){
    cs = argv[1];
  }
  else {
    cs = "abcd";
  }
  bool used[cs.length()];
  for(int i = 0;i<(int)cs.length();i++){
    used[i] = false;
  }
  int c = permutation("",cs,used);
  cout<<"#recursive calls is \t"<<c<<endl;

  cout<<"------------------------"<<endl;
  for(int i = 0;i<(int)cs.length();i++){
    used[i] = false;
  }
  c = permutation2("",cs,used);
  cout<<"#recursive calls is \t"<<c<<endl;
  return 0;
}
